//https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=23296&ru=%2Fpractice%2F12d959b108cb42b1ab72cef4d36af5ec&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 1.判断是否为质数:开根号；https://blog.csdn.net/m0_57362922/article/details/126129102
// 解法1:首先判断是不是满足质数因子只有2或者3或者5，但是这个时间复杂比较高；
// 解法2:使用红黑树：堆排序 + 去重的性质；防止越界使用long 类型；

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<bits/stdc++.h>

using namespace std;

int function_zhishu1() {
	int n;
	cin>>n;
	bool flag=1;
	for(int i=2;i<sqrt(n);i++){
		if(n%i==0){
			flag=0;
			break;
		}
	}
	if(flag)cout<<"YES";
	else cout<<"NO";
	return 0;
}

class Solution1 {
public:
    int IsUgly(int index) {
        // write code here
        while (index%2 == 0) {
            index /=2;
        }
        while (index%3 == 0) {
            index /=3;
        }
        while (index%5 == 0) {
            index /=5;
        }
        return index == 1? true:false;
    }
    int GetUglyNumber_Solution(int index) {
        if (index <=0) return 0;
        int number = 0;
        int uglyfound = 0;
        while(uglyfound<index){
            ++number;
            if(IsUgly(number)) {    
                ++uglyfound;
            }
        }
        return number;
    }
};

class Solution2 {
  public:
    int GetUglyNumber_Solution(int index) {

        if (index <= 0 ) return 0;
        int cur_index = 0;
        long number = 0;

        std::set<long> tmp_set;
        tmp_set.insert(1);
        while (cur_index < index) {
            if (tmp_set.empty()) {
                break;
            }
            number = *(tmp_set.begin());
            auto v1 = 2 * number;
            auto v2 = 3 * number;
            auto v3 = 5 * number;
            if (v1 > 0) tmp_set.insert(v1);
            if (v2 > 0) tmp_set.insert(v2);
            if (v3 > 0) tmp_set.insert(v3);
            
            tmp_set.erase(tmp_set.begin());
            if (number != 1) {
                if (number * number > 0)
                    tmp_set.insert(number * number);
            }
            ++cur_index;
        }
        return number;
    }
};


